/*
784. 字母大小写全排列
给定一个字符串S，通过将字符串S中的每个字母转变大小写，我们可以获得一个新的字符串。返回所有可能得到的字符串集合。

示例:
输入: S = "a1b2"
输出: ["a1b2", "a1B2", "A1b2", "A1B2"]

输入: S = "3z4"
输出: ["3z4", "3Z4"]

输入: S = "12345"
输出: ["12345"]

注意：

    S 的长度不超过12。
    S 仅由数字和字母组成。
*/

#include <string>
#include <vector>
using namespace std;

class Solution
{
public:
    vector<string> letterCasePermutation(string S)
    {
        vector<string> ret;
        ret.push_back(S);
        for(int i = 0; i < S.size(); i++) {
            if(S[i] > '9') {
                int k = ret.size();
                for(int j = 0; j < k; j++) {
                    string tmp = ret[j];
                    tmp[i] ^= 32; // 97-65
                    ret.push_back(tmp);
                }
            }
        }
        return ret;
    }
};

/*未验证*/
class Solution
{
private:
    void dfs(const string &S, int cur, string &s, vector<string> &ans)
    {
        if(cur >= S.length()) {
            ans.push_back(s);
            return;
        }
        s.push_back(S[cur]);
        dfs(S, cur + 1, s, ans);
        s.pop_back();
        if(S[cur] > '9') {
            s.push_back(S[cur] ^ 32);
            dfs(S, cur + 1, s, ans);
            s.pop_back();
        }
    }

public:
    vector<string> letterCasePermutation(string S)
    {
        int            len = (int)S.size();
        vector<string> ans;
        string         s = "";
        dfs(S, 0, s, ans);
        return ans;
    }
};